package LinkedList;

import demo.IndexNotLegalException;
import lianbiaoti.AA;

public class MyLinkedList {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;



       public void addFirst(int data) {
           ListNode listNode=new ListNode(data);
           if(head==null){
               head=listNode;
               last=listNode;
           }else {
               listNode.next=head;
               head.prev=listNode;
               head=listNode;
           }

       }


       public void addLast(int data){
           ListNode listNode=new ListNode(data);
           if(head==null) {
               head = listNode;
               last = listNode;
           }else {
               last.next=listNode;
               listNode.prev=last;
               last=listNode;//或者last=last.next
           }
       }


     public void addIndex(int index,int data){
           ListNode listNode=new ListNode(data);
           if (head==null){
               head=listNode;
               last=listNode;
           }
           if (index<0||index>size()){
               throw new IndexNotLegalException("双向列表index不合法");
           }
           if (index==0){
               addFirst(data);
           }
           if (index==size()){
               addLast(data);
           }
          ListNode cur=findIndex(index);
           listNode.next=cur;
           cur.prev.next=listNode;
           listNode.prev=cur.prev;
           cur.prev=listNode;

     }
     public ListNode findIndex(int index){
           ListNode cur=head;
           while(index!=0){
               cur=cur.next;
               index--;
           }
           return cur;
     }


          public boolean contains(int key){
              ListNode cur=head;
              while(cur!=null){
                  if (cur.val==key){
                      return true;
                  }
                  cur=cur.next;
              }
             return false;
          }


        public void remove(int key){
           ListNode cur=head;
           while(cur!=null){
               if (cur.val==key){
                   if (cur==head){
                       head=head.next;
                       //防止只有一个节点
                       if (head!=null) {
                           head.prev = null;
                       }
                   }else {
                       cur.prev.next = cur.next;
                       if (cur.next!=null) {//删除的不是尾巴节点
                           cur.next.prev = cur.prev;
                       }else {//删除的是尾巴节点
                           last=cur.prev;
                       }

                   }
                   return;
               }
               cur=cur.next;
           }

        }


        public void removeAllKey(int key){
            ListNode cur=head;
            while(cur!=null){
                if (cur.val==key){
                    if (cur==head){
                        head=head.next;
                        //防止只有一个节点
                        if (head!=null) {
                            head.prev = null;
                        }
                    }else {
                        cur.prev .next= cur.next;
                        if (cur.next!=null) {
                            cur.next.prev = cur.prev;
                        }else {
                            last=cur.prev;
                        }

                    }
                }
                cur=cur.next;
            }

        }


         public int size(){
             ListNode cur=head;
             int count=0;
             while(cur!=null){
                 count++;
                 cur=cur.next;
             }
             return count;
         }
  public void display(){
           ListNode cur=head;
           while(cur!=null){
               System.out.print(cur.val+" ");
               cur=cur.next;
           }
      System.out.println();
  }
 public void clear(){
        ListNode cur=head;
        while(cur!=null) {
            ListNode curNext = cur.next;
            cur.next=null;
            cur.prev=null;
            cur=curNext;
        }
        head=null;
        last=null;

    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.addLast(20);
        myLinkedList.addLast(20);
        myLinkedList.addLast(10);
        myLinkedList.addLast(10);
        myLinkedList.addLast(2);
        myLinkedList.addLast(20);

        myLinkedList.removeAllKey(20);
    myLinkedList.display();
    }
}
